'''
Created on 2010-3-2

@author: Administrator
'''
from jolly.datastructures.Queue import Queue
from jolly.datastructures.LinkedList import LinkedList
from jolly.datastructures.Iterator import Iterator
from jolly.datastructures.Visitor import Visitor
from jolly.datastructures.Exception import *

class QueueAsLinkedList(Queue):
    '''
    Queue implemented using a linked list
    '''


    def __init__(self):
        '''
        (QueueAsLinkedList)->None
        Constructs a queue
        The _list instance attribute is an instance of the LinkedList class.
        It is used to keep track of the elements in the queue
        '''
        super(QueueAsLinkedList, self).__init__()
        self._list = LinkedList()
    
    def purge(self):
        '''
        (QueueAsLinkedList)->None
        Purges this queue
        '''
        self._list.purge()
        self._count = 0
    
    def getHead(self):
        '''
        (QueueAsLinkedList) -> Object
        Returns the object at the head of this queue
        '''
        if self._count == 0:
            raise ContainerEmpty
        # orgin: return self._list.first, but it really so return the obj nor the
        # list' elment
        return self._list.first.datum
    
    def enqueue(self, obj):
        '''
        (QueueAsLinkedList, Object)-> None
        Enqueues the given object to the tail of this queue.
        '''
        self._list.append(obj)
        self._count+= 1
    
    def dequeue(self):
        '''
        (QueueAsLinkedList)->Object
        Dequeue the object at the head of this queue.
        '''
        if self._count==0:
            raise ContainerEmpty
        # here orign: result=self._list.first but so modify:result=self._list.first.datum
        result=self._list.first.datum
        self._list.extract(result)
        self._count-=1
        return result
    
    def accept(self, visitor):
        '''
        (QueueAsLinkedList, Visitor)->None
        Makes the given visitor visit all the object in this queue.
        '''
        assert isinstance(visitor, Visitor)
        ptr = self._list.head
        while ptr is not None:
            visitor.visit(ptr.datum)
            if visitor.isDone:
                return 
            ptr = ptr.next
    
    class Iterator(Iterator):
        '''
        Enumerates the elements of a QueueAsLinkedList.
        '''
        
        def __init__(self, queue):
            '''
            (QueueAsLinkedList.Iterator, QueueAsLinkedList)->None
            Constructs an iterator for the given queue.
            '''
            super(QueueAsLinkedList.Iterator).__init__(queue)
            self._position = None
        
        def next(self):
            '''
            (QueueAsLinkedList.Iterator).__init__(queue)
            Returns the next element.
            '''
            if self._position is None:
                self._position=self._container._list.head
            else:
                self._position=self._position.next
            if self._position is None:
                raise StopIteration
            return self._position.datum
        
    def __iter__(self):
        '''
        (QueueAsLinkedList)->QueueAsLinkedList.Iterator
        Returns an iterator for this queue.
        '''
        return self.Iterator(self)
    
    def _compareTo(self, obj):
        '''
        (QueueAsLinkedList, QueueAsLinkedList)->int
        Compare this queue with the given queue
        '''
        assert isinstance(self, obj.__class__)
        raise NotImplementedError
    
    @staticmethod
    def main(*argv):
        "QueueAsLinkedList test program."
        print QueueAsLinkedList.main.__doc__
        queue2 = QueueAsLinkedList()
        Queue.test(queue2)
        return 0
    
if __name__ == "__main__":
    sys.exit(QueueAsLinkedList.main(*sys.argv))